package chapter03_binaryTree;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * 描述：
 *      统计和生成所有的二叉树
 * @author hl
 * @date 2021/6/2 15:12
 */
public class NumAndGenerateTree {
    public static void main(String[] args) {
        NumAndGenerateTree main = new NumAndGenerateTree();
        int i = main.numTree(10);
        System.out.println(i);
        List<Node> nodes = main.generateTrees(2);
        System.out.println(nodes);
    }

    /**
     * 统计1...n的为结点按照中序遍历可以生成多少棵二叉树
     * 注意:因为是中序遍历而且结点值无重复,那么生成的二叉树的个数就只与结点数相关了,可以用num(a)表示a个结点的搜索二叉树有多少坑你
     *
     *  那么如果以i为头的二叉树结构就有Num(i - 1) * Num(n - i)种，因此可以用动态规划进行加速
     * @param n
     * @return
     */
    public int numTree(int n){
        if (n < 2) {
            return 1;
        }
        int[] num = new int[n + 1];
        num[0] = 1;
        for (int i = 1; i <= n; i++) {
            //以j为根结点
            for (int j = 1; j <= i; j++) {
                num[i] += num[j - 1] * num[i - j];
            }
        }
        return num[n];
    }

    public List<Node> generateTrees(int n){
        return generate(1, n);
    }

    private List<Node> generate(int l, int r) {
        List<Node> res = new ArrayList<>();
        if (l > r) {
            res.add(null);
            return res;
        }
        List<Node> listLeft = null;
        List<Node> listRight = null;
        Iterator<Node> li = null;
        Iterator<Node> ri = null;
        for (int i = l; i <= r; i++) {
            Node head = new Node(i);
            listLeft = generate(l, i - 1);
            listRight = generate(i + 1, r);
            li = listLeft.iterator();
            ri = listRight.iterator();
            while(li.hasNext()){
                while (ri.hasNext()){
                    head.left = li.next();
                    head.right = ri.next();
                    res.add(cloneTree(head));
                }
            }
        }
        return res;
    }

    private Node cloneTree(Node head) {
        if (head == null) {
            return null;
        }
        Node node = new Node(head.val);
        node.left = cloneTree(head.left);
        node.right = cloneTree(head.right);
        return node;
    }

    /*public int numTree2(int n){
        return process(1, n);
    }

    private int process(int l, int r) {
        if (l >= r) {
            return 1;
        }
        int res = 0;
        for (int i = l; i <= r; i++) {
            res += process(l, i - 1) * process(i + 1, r);
        }
        return res;
    }*/
}
